"""
五子棋AI层
实现AI智能体的决策逻辑
"""

import random
from typing import Tuple, List


class GobangAI:
    """五子棋AI基类"""
    
    def __init__(self, player_id):
        """
        初始化AI
        :param player_id: AI的玩家ID（1或2）
        """
        self.player_id = player_id
        
    def get_move(self, game_rules):
        """
        获取AI的落子位置
        :param game_rules: GobangRules实例
        :return: (row, col) 落子位置
        """
        raise NotImplementedError("子类必须实现get_move方法")


class RandomAI(GobangAI):
    """随机AI，随机选择合法位置落子"""
    
    def get_move(self, game_rules):
        """随机选择一个合法位置"""
        valid_moves = game_rules.get_valid_moves()
        if valid_moves:
            return random.choice(valid_moves)
        return None


class GreedyAI(GobangAI):
    """贪心AI，基于启发式评估函数选择最佳位置"""
    
    def __init__(self, player_id):
        super().__init__(player_id)
        self.opponent_id = 3 - player_id  # 对手ID
        
    def get_move(self, game_rules):
        """使用启发式评估选择最佳位置"""
        valid_moves = game_rules.get_valid_moves()
        if not valid_moves:
            return None
        
        best_score = -float('inf')
        best_moves = []
        
        for row, col in valid_moves:
            score = self.evaluate_position(game_rules, row, col)
            if score > best_score:
                best_score = score
                best_moves = [(row, col)]
            elif score == best_score:
                best_moves.append((row, col))
        
        return random.choice(best_moves) if best_moves else None
    
    def evaluate_position(self, game_rules, row, col):
        """
        评估某个位置的价值
        :param game_rules: GobangRules实例
        :param row: 行坐标
        :param col: 列坐标
        :return: 位置分数
        """
        score = 0
        
        # 评估自己落子后的得分
        score += self.evaluate_player_score(game_rules, row, col, self.player_id) * 1.0
        
        # 评估阻止对手的得分
        score += self.evaluate_player_score(game_rules, row, col, self.opponent_id) * 0.9
        
        return score
    
    def evaluate_player_score(self, game_rules, row, col, player_id):
        """
        评估某个玩家在指定位置的得分
        :param game_rules: GobangRules实例
        :param row: 行坐标
        :param col: 列坐标
        :param player_id: 玩家ID
        :return: 分数
        """
        score = 0
        board = game_rules.board
        
        # 四个方向：横、竖、左斜、右斜
        directions = [
            (0, 1),   # 横向
            (1, 0),   # 纵向
            (1, 1),   # 左上到右下
            (1, -1)   # 右上到左下
        ]
        
        for dx, dy in directions:
            # 统计该方向上的连续棋子数
            count = 1  # 包括当前位置
            empty_ends = 0  # 两端空位数
            
            # 正向检查
            x, y = row + dx, col + dy
            while 0 <= x < game_rules.board_size and 0 <= y < game_rules.board_size:
                if board[x][y] == player_id:
                    count += 1
                    x += dx
                    y += dy
                elif board[x][y] == 0:
                    empty_ends += 1
                    break
                else:
                    break
            
            # 反向检查
            x, y = row - dx, col - dy
            while 0 <= x < game_rules.board_size and 0 <= y < game_rules.board_size:
                if board[x][y] == player_id:
                    count += 1
                    x -= dx
                    y -= dy
                elif board[x][y] == 0:
                    empty_ends += 1
                    break
                else:
                    break
            
            # 根据连子数和空端数评分
            score += self.calculate_pattern_score(count, empty_ends)
        
        return score
    
    def calculate_pattern_score(self, count, empty_ends):
        """
        根据连子模式计算分数
        :param count: 连子数
        :param empty_ends: 空端数（0, 1, 2）
        :return: 分数
        """
        if count >= 5:
            return 100000  # 五连，必胜
        
        if empty_ends == 0:
            return 0  # 两端被堵，无威胁
        
        if count == 4:
            if empty_ends == 2:
                return 10000  # 活四
            else:
                return 1000   # 冲四
        
        if count == 3:
            if empty_ends == 2:
                return 1000   # 活三
            else:
                return 100    # 眠三
        
        if count == 2:
            if empty_ends == 2:
                return 100    # 活二
            else:
                return 10     # 眠二
        
        if count == 1:
            if empty_ends == 2:
                return 10     # 活一
            else:
                return 1      # 眠一
        
        return 0


class MinimaxAI(GobangAI):
    """Minimax算法AI（带Alpha-Beta剪枝）"""
    
    def __init__(self, player_id, depth=2):
        super().__init__(player_id)
        self.opponent_id = 3 - player_id
        self.depth = depth  # 搜索深度
        self.greedy_ai = GreedyAI(player_id)  # 使用贪心AI的评估函数
        self.nodes_searched = 0  # 统计搜索节点数（用于调试）
        
    def get_move(self, game_rules):
        """使用Alpha-Beta剪枝的Minimax算法选择最佳位置"""
        valid_moves = game_rules.get_valid_moves()
        if not valid_moves:
            return None
        
        # 为了提高效率，只考虑周围有棋子的位置
        candidate_moves = self.get_candidate_moves(game_rules)
        if not candidate_moves:
            # 如果是第一步，下在中心附近
            center = game_rules.board_size // 2
            return (center, center)
        
        # 重置节点计数
        self.nodes_searched = 0
        
        best_score = -float('inf')
        best_move = None
        alpha = -float('inf')
        beta = float('inf')
        
        for row, col in candidate_moves:
            # 模拟落子
            game_rules.make_move(row, col)
            
            # Alpha-Beta剪枝Minimax评估
            score = self.alpha_beta(game_rules, self.depth - 1, alpha, beta, False)
            
            # 撤销落子
            game_rules.undo_move()
            
            if score > best_score:
                best_score = score
                best_move = (row, col)
            
            # 更新alpha值
            alpha = max(alpha, best_score)
        
        return best_move
    
    def alpha_beta(self, game_rules, depth, alpha, beta, is_maximizing):
        """
        Alpha-Beta剪枝算法
        :param game_rules: GobangRules实例
        :param depth: 当前搜索深度
        :param alpha: Alpha值（最大化玩家的最好选择）
        :param beta: Beta值（最小化玩家的最好选择）
        :param is_maximizing: 是否是最大化玩家
        :return: 评估分数
        """
        self.nodes_searched += 1
        
        # 终止条件：游戏结束或达到最大深度
        if game_rules.game_over or depth == 0:
            return self.evaluate_board(game_rules)
        
        candidate_moves = self.get_candidate_moves(game_rules)
        if not candidate_moves:
            return 0
        
        if is_maximizing:
            max_eval = -float('inf')
            for row, col in candidate_moves:
                game_rules.make_move(row, col)
                eval = self.alpha_beta(game_rules, depth - 1, alpha, beta, False)
                game_rules.undo_move()
                
                max_eval = max(max_eval, eval)
                alpha = max(alpha, eval)
                
                # Beta剪枝：如果alpha >= beta，后续分支无需搜索
                if beta <= alpha:
                    break  # 剪枝
            return max_eval
        else:
            min_eval = float('inf')
            for row, col in candidate_moves:
                game_rules.make_move(row, col)
                eval = self.alpha_beta(game_rules, depth - 1, alpha, beta, True)
                game_rules.undo_move()
                
                min_eval = min(min_eval, eval)
                beta = min(beta, eval)
                
                # Alpha剪枝：如果beta <= alpha，后续分支无需搜索
                if beta <= alpha:
                    break  # 剪枝
            return min_eval
    
    def evaluate_board(self, game_rules):
        """
        评估当前棋盘局面
        :param game_rules: GobangRules实例
        :return: 评估分数
        """
        if game_rules.game_over:
            if game_rules.winner == self.player_id:
                return 1000000  # AI获胜
            elif game_rules.winner == self.opponent_id:
                return -1000000  # 对手获胜
            else:
                return 0  # 平局
        
        # 使用贪心AI的评估函数
        score = 0
        for row in range(game_rules.board_size):
            for col in range(game_rules.board_size):
                if game_rules.board[row][col] == 0:
                    my_score = self.greedy_ai.evaluate_player_score(game_rules, row, col, self.player_id)
                    opp_score = self.greedy_ai.evaluate_player_score(game_rules, row, col, self.opponent_id)
                    score += my_score - opp_score
        
        return score
    
    def get_candidate_moves(self, game_rules):
        """
        获取候选落子位置（周围有棋子的空位）
        :param game_rules: GobangRules实例
        :return: 候选位置列表
        """
        candidate_set = set()
        board = game_rules.board
        
        for row in range(game_rules.board_size):
            for col in range(game_rules.board_size):
                if board[row][col] != 0:
                    # 检查周围的空位
                    for dr in [-1, 0, 1]:
                        for dc in [-1, 0, 1]:
                            if dr == 0 and dc == 0:
                                continue
                            nr, nc = row + dr, col + dc
                            if (0 <= nr < game_rules.board_size and 
                                0 <= nc < game_rules.board_size and 
                                board[nr][nc] == 0):
                                candidate_set.add((nr, nc))
        
        return list(candidate_set)
